package 动态规划.背包And分组And切割问题系列;

public class leetcode6244 {

	public static final int cons = 1000000007;
	public static boolean [] flag = {false, false, true, true, false, true, false, true, false, false};
	
	
	public static int solution(String s,int k,int minLength) {
		int len = s.length();
		if(len < k * minLength)
			return 0;
		char str [] = s.toCharArray(); 
//		return recursion(0,);
		return 0;
	}
	
	public static int recursion(int index,char str[] ,int k,int minLength,int len) {
		if(index == len)
			return  k == 0 ? 1 : 0;
		if(!flag[str[index ] - '0'])
			return 0;

		int ans = 0;		
		for(int scale = minLength;index + len <= len; scale ++) {
			if(flag[str[index + scale - 1] - '0'])
				continue;
			ans += recursion(index + scale,str,k - 1,minLength,len);
		}
		return ans;
	
	}
	/**
	 * 这个时间 复杂度 已经  ac 了
	 * 不过 这个题 是真的  离谱 啊 ！
	 */
	public static int dp(String s,int k,int minLength) {
		int len = s.length();
		long dp[][] = new long [len + 1][k + 1];
		char str [] = s.toCharArray(); 
		dp[len][0] = 1;
		for(int index = len - 1;index >= 0; index --) {
			if(!flag[str[index] - '0'])
				continue;
			for(int x = 1;x <= k ;x++) {
				long ans = 0L;
				for(int scale = minLength; index + scale <= len; scale++) {
					if(flag[str[index + scale - 1] - '0'])
						continue;
//					dp[index][x] += dp[index + scale][x - 1];
					ans += dp[index + scale][x - 1];
				}
				ans %= cons;
				dp[index][x] = ans; 
			}
		}
		return (int)dp[0][k];
	}
	public static void main(String args[]) {
		String s = "7753639519183359148598823162755335682921461647796985255166979917649578972791819356618496239687361868933775339936875893219782348459522657159781118588765368954599285197845124455559747963186111993765269";
		int k = 24;
		int minLength = 2;
		System.out.println(dp(s,k,minLength));
	}
	
	
}
